#include "Multitree.h"
#include "Tuplets.h"
#include <assert.h>
#include <gc/gc.h>


Multitree * add_and_multiply(enum OperatorType oper, ListOfChilds * childs);
Multitree * function_values(Multitree * tree);

Multitree * canonicalize_tree(Multitree * tree){
	if (tree == NULL){
		return NULL;
	}
	Multitree * one = copy_tree(tree);
	Multitree * two = reduce_tree(one);
	if(two == NULL){
		return NULL;
	}
	Multitree * tmp = NULL;
	rehang_tree(two);
	sort_tree(two);
	/*Reduce tree, until nothing more can be done 
	(when calling rehang, some nodes can come up that could be reduced more)*/
	while (treecmp(one, two) != 0){
		delete_tree(one);
		one = reduce_tree(two);
		if(one == NULL){
			return NULL;
		}
		rehang_tree(one);
		sort_tree(one);
		tmp = two;
		two = one;
		one = tmp;
	}
	/*two and one are now identical.*/
	delete_tree(one);
	one = NULL;
	tmp=NULL;
	return two;
}




Multitree * reduce_tree(Multitree * tree){
	/*This function reduces tree - it prunes parts like 0*<something> and similar*/
	Multitree * to_return = NULL;
	Multitree * argument = NULL;
	Multitree * tmp = NULL;
	ListOfChilds * pass = NULL;
	ListOfChilds * childs = NULL;
	Number * one;
	Number * zero;
	one = construct_number();
	zero = construct_number();
	inttonum(one, 1);
	inttonum(zero, 0);
	if(tree == NULL){
		return NULL;
	}
	
	switch(tree->symbol.type){
		case CONSTANT:
		case VARIABLE:
		case NUMBER:
			/*We do nothing*/
			return copy_tree(tree);
			break;
		case FUNCTION:
			/*We edit subtree and then put it as argument of the function (we make copy of this node)
			We can of course find the value of the functions.*/
			argument = reduce_tree(tree->childs->subtree);
			if(argument == NULL){
				return NULL;
			}
			to_return = give_me_empty_tree();
			symbolcpy(&(to_return->symbol), &(tree->symbol));
			to_return->childs = give_me_empty_child();
			to_return->childs->inverted = 0; 
			to_return->childs->next = NULL;
			to_return->childs->subtree = argument;
			if (argument->symbol.type == NUMBER){
				tmp = function_values(to_return);
				delete_tree(to_return);
				to_return = tmp;
			}

			return to_return;
			break;
		case OPERATOR:
			/*Reduce childs first. And put them back in same order!
			There is at least one child (in fact there are at least two)*/
			pass = tree->childs;
			childs = give_me_empty_child();
			childs->inverted = pass->inverted;
			childs->next = NULL;
			childs->subtree = reduce_tree(pass->subtree);
			if(childs->subtree == NULL){
				return NULL;
			}
			ListOfChilds * added = childs;
			pass = pass->next;
			while (pass != NULL){
				added->next = give_me_empty_child();
				added = added->next;
				added->inverted = pass->inverted;
				added->next = NULL;
				added->subtree = reduce_tree(pass->subtree);
				if(added->subtree == NULL){
					return NULL;
				}
				pass = pass->next;
			}
			/*Childs are reduced. What now?*/

			/*if it is power, then do something special if it is 1^<something> or 0^<something> or <something>^0*/
			
			if (tree->symbol.oper == POWER){
				if((childs->subtree->symbol.type == NUMBER)
					&& (numbercmp(childs->subtree->symbol.number, one) == 0)){
						to_return = inttotree(1);
						delete_childs(childs);
						return to_return;
				}

				/*something to 0 is 1*/
				/*even zero to zero - but it can be changed here*/
				if((childs->next->subtree->symbol.type == NUMBER)
					&& (numbercmp(childs->next->subtree->symbol.number, zero) == 0)){
						to_return = inttotree(1);
						delete_childs(childs);
						return to_return;
				}

				/*0 to something is 0.*/
				if((childs->subtree->symbol.type == NUMBER)
					&& (numbercmp(childs->subtree->symbol.number, zero) == 0)){
						to_return = inttotree(0);
						delete_childs(childs);
						return to_return;
				}

				/*Something to 1 is that something*/
				if((tree->childs->next->subtree->symbol.type == NUMBER)
					&& (numbercmp(tree->childs->next->subtree->symbol.number, one) == 0)){
						to_return = copy_tree(tree->childs->subtree);
						delete_childs(childs);
						return to_return;
				}

				/*In other cases return power with reduced childs.*/

				to_return = give_me_empty_tree();
				symbolcpy(&(to_return->symbol), &(tree->symbol));
				to_return->childs = childs;
				return to_return;
				break;
			}else{
				/*Now we have plus or multiply. We pass list of childs there and return something*/
				to_return = add_and_multiply(tree->symbol.oper, childs);
				delete_childs(childs);
				if(to_return == NULL){
					return NULL;
				}
				return to_return;
			}
	}
	return NULL;
}

Multitree * add_and_multiply(enum OperatorType oper, ListOfChilds * childs){
	Number * number=NULL;
	Number * zero=NULL;
	Number * one=NULL;
	Multitree * to_return = NULL;
	ListOfChilds * pass = NULL;
	ListOfChilds * added = NULL;
	ListOfChilds * newchilds = NULL;
	ListOfChilds * oldchilds = NULL;
	Multitree * tmp = NULL;
	Multitree * tree = NULL;
	Tuplet * a = NULL;
	Tuplet * b = NULL;
	one = construct_number();
	zero = construct_number();
	number = construct_number();
	inttonum(zero, 0);
	inttonum(one, 1);

	/*First we want to bring some childs up.
	We create new tree, rehang it and then delete its top node (childs are enough).*/
	tree = give_me_empty_tree();
	tmp = NULL;
	tree->symbol.type = OPERATOR;
	tree->symbol.oper = oper;
	tree->childs = childs;
	/*We created new tree, but put there old childs. We copy it to new one so that we get new childs.*/
	tmp = copy_tree(tree);
	GC_FREE(tree); /*free node, not childs*/
	tree = tmp;
	tmp = NULL;
	/*Now we rehang it*/
	rehang_tree(tree);
	sort_tree(tree);
	/*point the pass to its childs*/
	pass = tree->childs;
	oldchilds = pass;
	/*and delete topmost node.*/
	GC_FREE(tree);
	tree = NULL;
	
	/*Now we add numbers as we need.*/
	if(oper == MULTIPLY){
		inttonum(number, 1);
		while(pass != NULL){
			if(pass->subtree->symbol.type == NUMBER){
				if(pass->inverted){
					if (numbercmp(pass->subtree->symbol.number, zero) == 0){
						return NULL;
					}
					/*assert(("Nulou sa nedeli.", (numbercmp(pass->subtree->symbol.number, zero) != 0)));*/
					numberdiv(number, number, pass->subtree->symbol.number);
				}else{
					numbermul(number, number, pass->subtree->symbol.number);
				}
			}else{
				added = give_me_empty_child();
				added->subtree = copy_tree(pass->subtree);
				added->inverted = pass->inverted;
				added->next = newchilds;
				newchilds = added;
			}
			pass = pass->next;
		}
		added = NULL;
		/*Maybe we should have done the same with constants, not only numbers. Nevermind.
		If number is 0, then we return zero.*/
		if(numbercmp(number, zero) == 0){
			/*We return 0 in the tree.*/
			delete_childs(newchilds);
			to_return = inttotree(0);
			return to_return;
		}
		/*if it is 1, we do not attach it.*/
		if(numbercmp(number, one) != 0){
			added = give_me_empty_child();
			added->inverted = 0;
			added->subtree = treefromnum(number);
			if(added->subtree == NULL){
				return NULL;
			}
			added->next = newchilds;
			newchilds = added;
		}
	}else{
		/*assert(oper == PLUS);
		We basically copy the whole thing.*/
		inttonum(number, 0);
		while(pass != NULL){
			if(pass->subtree->symbol.type == NUMBER){
				if(pass->inverted){
					numberminus(number, number, pass->subtree->symbol.number);;
				}else{
					numberplus(number, number, pass->subtree->symbol.number);
				}
			}else{
				added = give_me_empty_child();
				added->subtree = copy_tree(pass->subtree);
				added->inverted = pass->inverted;
				added->next = newchilds;
				newchilds = added;
			}
			pass = pass->next;
		}
		added = NULL;
		//We just do not connect 0 to the beginning of this.
		if(numbercmp(number, zero) != 0){
			added = give_me_empty_child();
			added->inverted = 0;
			added->subtree = treefromnum(number);
			if(added->subtree == NULL){
				return NULL;
			}
			added->next = newchilds;
			newchilds = added;
		}
	}
	
	/*Now we have the fully prepared childs in newchilds. We can delete oldchilds.
	delete_childs(oldchilds);
	Do with newchilds, what has to be done.*/
	

	/*This part adds or multiplies "compatible" subtrees.
	For example 2*x+3*x = 5*x or cos(y)^6/cos(y)^2 = cos(y)^4
	It creates new tree and does not do it inplace*/
			
	/*We convert childs to tuplets, add tuplets, remove unnecessary tuplets and convert it back to list.*/
	a = childs_to_tuplets(oper, newchilds);
	/*??
	 if(a == NULL){
		return NULL;
	}*/
	/*We can delete childs*/
	delete_childs(newchilds);
	newchilds = NULL;
	b = add_tuplets(a);
	delete_tuplets(a);
	a = NULL;
	a = remove_null_tuplets(b);
	delete_tuplets(b);
	b = NULL;
	newchilds = tuplets_to_childs(oper, a);
	/*this can be null*/
	delete_tuplets(a);
	a = NULL;
	
	/*So we have new list of childs. Now, depending on the number of childs, we return tree.*/
	
	if (newchilds == NULL){
		/*No childs*/
		if(oper == MULTIPLY){
			to_return = inttotree(1);
		}else{
			to_return = inttotree(0);
		}
		return to_return;
	}

	if(newchilds->next == NULL){
		/*One child.*/
		/*If not inverted*/
		if(!(newchilds->inverted)){
			to_return = newchilds->subtree;
			GC_FREE(newchilds);
			newchilds = NULL;
			return to_return;
		}else{
			/*It is inverted, we return operator with two childs
			Either -1*child or child^-1*/
			to_return = give_me_empty_tree();
			to_return->symbol.type = OPERATOR;
			
			to_return->childs = give_me_empty_child();
			to_return->childs->inverted = 0;
			to_return->childs->next = give_me_empty_child();
			to_return->childs->next->next = NULL;
			to_return->childs->next->inverted = 0;

			if(oper == MULTIPLY){
				to_return->symbol.oper = POWER;
				to_return->childs->subtree = newchilds->subtree;
				to_return->childs->next->subtree = inttotree(-1);
			}else{
				to_return->symbol.oper = MULTIPLY;
				to_return->childs->subtree = inttotree(-1);
				to_return->childs->next->subtree = newchilds->subtree;
			}
			GC_FREE(newchilds);
			return to_return;
		}
	}
	/*There are more than one newchild*/
	to_return = give_me_empty_tree();
	to_return->symbol.type = OPERATOR;
	to_return->symbol.oper = oper;
	to_return->childs = newchilds;
	sort_tree(to_return);
	return to_return;
}

Multitree * function_values(Multitree * tree){
	/*If the value of the function is known (basically if its argument is zero) then return that value.
	otherwise do not change the tree.*/
	Number * zero;
	Number * one;
	Multitree * to_return = NULL;
	zero = construct_number();
	one = construct_number();
	inttonum(zero, 0);
	inttonum(one, 1);
	if(tree == NULL){
		return NULL;
	}

	if (tree->symbol.type != FUNCTION){
		return copy_tree(tree);
	}

	if (tree->childs->subtree->symbol.type != NUMBER){
		return copy_tree(tree);
	}


	switch(tree->symbol.func){
		case SIN:
		case TAN:
		case COS:
			if (numbercmp(tree->childs->subtree->symbol.number, zero) == 0){
				if (tree->symbol.func == COS){
					to_return = inttotree(1);
				}else{
					to_return = inttotree(0);
				}
				return to_return;
			}
			break;
		case LN:
			/*for logarithm our number is one*/
			if (numbercmp(tree->childs->subtree->symbol.number, one) == 0){
				to_return = inttotree(0);
				return to_return;
			}
			break;
	}
	return copy_tree(tree);
}
